package com.suanfa.dp;

/**
 * A-》1 B->2  Z->26  字母映射
 */
public class NumerEncode {

    char[] ch = {'1','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O',
            'P','Q','R','S','T','U','V','W','X','Y','Z'};

    public static void main(String[] args) {
        String s = "12";
        System.out.println(numDecodings(s));
        System.out.println(numDecodings2(s));
    }

    /**
     * dp[i] = dp[i-1]  s[i] [1,9]
     * dp[i] = dp[i-2]  s[i-1] s[i] [10,26]
     * @param s
     * @return
     */
    public static int numDecodings(String s) {
        if(s.startsWith("0")){
            return 0;
        }
        int length = s.length();

        s = " " + s;
        char[] ch = s.toCharArray();
        int[] dp = new int[length+1];

        dp[0] = 1;

        for(int i = 1; i<= length; i++){
            int a = ch[i] - '0';
            int b = (ch[i-1] - '0')* 10 + (ch[i] - '0');

            if(a>0 && a < 10){
                dp[i] = dp[i-1];
            }

            if(b > 9 && b< 27){
                dp[i] += dp[i-2];
            }

        }
        return dp[length];



    }

    public static int numDecodings2(String s) {
        int n = s.length();
        s = " " + s;
        char[] cs = s.toCharArray();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            // a : 代表「当前位置」单独形成 item
            // b : 代表「当前位置」与「前一位置」共同形成 item
            int a = cs[i] - '0', b = (cs[i - 1] - '0') * 10 + (cs[i] - '0');
            // 如果 a 属于有效值，那么 f[i] 可以由 f[i - 1] 转移过来
            if (1 <= a && a <= 9) f[i] = f[i - 1];
            // 如果 b 属于有效值，那么 f[i] 可以由 f[i - 2] 或者 f[i - 1] & f[i - 2] 转移过来
            if (10 <= b && b <= 26) f[i] += f[i - 2];
        }
        return f[n];
    }

}
